#ifndef BTREE_H
#define BTREE_H
// #define DEBUG
/**
 * @file BTree.h
 * @author linxi (linxi177229@gmail.com)
 * @brief 这个文件是基于模板的B-Tree的C++14实现，全部采用了move语义，以及智能指针
 * @version 0.1
 * @date 2022-02-21
 *
 * @copyright Copyright (c) 2022
 *
 */
#include <cstdio>
#include <memory>

#include "vector/vector.h"

/**
 * @brief 这是B树的实现，内部有一个BTNode作为其结点，BTree实际上就是一个unique_ptr<BTNode>
 * 另外，这个B树是很好的扩展，可以根据传入的T（key）进行不同的处理，只要重载了operator
 * ==，>，就可以很好的运用了 也可以修改一下search，以及外部结点，就可以变成B+树
 *
 */
template <class T>
class BTree {
   private:
    struct BTNode;

   public:
    using BTNodePtr = std::unique_ptr<BTNode>;
    using BTNodePosi = BTNode*;

   private:
    struct BTNode {
        BTNode(const BTNode&) = delete;
        BTNode& operator=(const BTNode&) = delete;
        // 无关键码结点, 会创建一个空节点儿子
        BTNode() : parent(nullptr) { child.emplace_back(nullptr); }
        // 一个关键码，且作为根结点
        BTNode(const T& e, BTNodePtr&& lc = nullptr, BTNodePtr&& rc = nullptr)
            : parent(nullptr), key{e}
        {
            if (lc != nullptr) lc->parent = this;
            if (rc != nullptr) rc->parent = this;
            child.push_back(std::move(lc));
            child.push_back(std::move(rc));
        }

        BTNodePosi parent;        // 父节点
        Vector<T> key;            //关键码向量
        Vector<BTNodePtr> child;  // 孩子向量
    };

   public:
    /**
     * @brief 创建一颗度为order的B树
     *
     * @param order
     */
    BTree(int order = 3) : size_(0), order_(order), root_(std::make_unique<BTNode>()), hot_(nullptr)
    {
    }
    // 对象语义，显式删去copy，移动的保留
    BTree(const BTree&) = delete;
    BTree& operator=(const BTree&) = delete;
    int order() const { return order_; }
    int size() const { return size_; }
    bool empty() const { return root_ == nullptr; }
    BTNodePosi root() const { return root_.get(); }  //调试用
    BTNodePosi search(const T& e);
    bool insert(const T& e);
    bool remove(const T& e);

   private:
    void solveOverflow(BTNodePosi);   // 因插入而上溢之后的分裂处理
    void solveUnderflow(BTNodePosi);  // 因下溢之后的合并处理
   private:
    int size_;   //关键码总数
    int order_;  // B-树的阶次，至少为3，一般不能修改
    BTNodePtr root_;
    BTNodePosi hot_;  // BTree::search()最后访问的非空（除非树空）结点的位置
};

/**
 * @brief 搜索值为e的结点，返回其地址，如果搜不到则返回nullptr
 *
 * @tparam T
 * @param e
 * @return BTree<T>::BTNodePosi
 */
template <class T>
typename BTree<T>::BTNodePosi BTree<T>::search(const T& e)
{
    auto v{root_.get()};
    hot_ = nullptr;  //从根节点出发
    while (v != nullptr) {
        // 找到 <= e的最大值的下标
        Rank searchPos = v->key.search(e);
        if (searchPos >= 0 && v->key[searchPos] == e) return v;
        hot_ = v;  // 最后访问的非空（除非树空）结点的位置
        v = v->child[searchPos + 1].get();  // 转入对应子树
    }
    return nullptr;  // 失败，返回外部结点
}
/**
 * @brief  插入key为e的结点，返回True，
 *
 * @tparam T
 * @param e
 * @return true  插入成功
 * @return false 如果结点已经存在，因为不支持重复插入那么返回false
 */
template <class T>
bool BTree<T>::insert(const T& e)
{
    auto v{this->search(e)};
    if (v != nullptr) return false;  // 不能重复插入
    auto r{hot_->key.search(e)};  // hot_是叶子结点，在这个向量上找到合适的位置
    hot_->key.insert(r + 1, e);   //将新关键码插至对应的位置
    hot_->child.insert(r + 2, nullptr);  // 新外部结点
    ++size_;
    solveOverflow(hot_);  // 如有必要，需要分裂
    return true;
}
/**
 * @brief 分裂v的孩子处理上溢 中位数结点移动到父节点，左右独立开
 *   1. 创建一个右儿子结点，将v右边的key，child移入其中
 *   2. 特判v是根结点需要，移动root_
 *   3. 将中位数结点移动到 v的父节点中
 *
 * @tparam T
 * @param v
 */
template <class T>
void BTree<T>::solveOverflow(BTNodePosi v)
{
    if (order_ >= v->child.size()) return;  //未上溢
    Rank s = order_ / 2;                    //中位数的位置
    auto u{std::make_unique<BTNode>()};     // u有一个空节点  是左儿子
    // 移动v的从s + 1开始的结点 给u
    u->key.insert(u->key.begin(), std::make_move_iterator(v->key.begin() + s + 1),
                  std::make_move_iterator(v->key.end()));
    u->child.pop_back();  // 这里要重点注意！nullptr是要被覆盖掉的
    u->child.insert(u->child.begin(), std::make_move_iterator(v->child.begin() + s + 1),
                    std::make_move_iterator(v->child.end()));
    v->key.resize(s + 1);  //后面会再pop_back(中位数)一次
    v->child.resize(s + 1);
    //因为insert过的点，必然是从front开始的，所以只用检测front即可判断孩子们是否非空
    if (u->child.front() != nullptr)  // 令u的孩子们 指向u
        for (const auto& child : u->child) child->parent = u.get();

    BTNodePosi father{v->parent};

    if (father == nullptr) {                        // v是根结点
        auto newRoot{std::make_unique<BTNode>()};   // 创建新的根节点
        father = newRoot.get();                     // 重新设置father
        v->parent = father;                         // v的parent 指向 新根
        newRoot->child.front() = std::move(root_);  // 新根的子节点 是原来的root_
        root_ = std::move(newRoot);                 // 换根
    }
    Rank r = 1 + father->key.search(v->key.front());  // 找到最大的<=key[0]的位置+1插入key[s]
    father->key.insert(r, std::move(v->key.back()));  // 轴点关键码上升
    v->key.pop_back();                                // v删去中位数这个结点
    u->parent = father;                               // 新儿子u与父节点p互联
    father->child.insert(r + 1, std::move(u));        // father连上新儿子
    solveOverflow(father);  //上升一层，如有必要则继续分裂——至多递归O(logn)层
}

/**
 * @brief 从BTree树中删除关键码e 真正删除的节点一定是一个叶子节点，即便e的key不是叶子，
 * 我们也可以通过交换并删除它的后继来达到此效果
 *
 * @param e
 * @return true 成功删除返回true
 * @return false 找不到结点返回false
 */
template <typename T>
bool BTree<T>::remove(const T& e)
{
    BTNodePosi v{search(e)};
    if (v == nullptr) return false;
    Rank r{v->key.search(e)};           //确定目标关键码的秩
    if (v->child.front() != nullptr) {  //若e非叶子节点，那么e的后继必属某叶节点
        BTNodePosi u{v->child[r + 1].get()};
        while (u->child[0] != nullptr) u = u->child[0].get();  // 右子树一直往左
        v->key[r] = std::move(u->key[0]);  // 换成最左边的key，也就是后继
        v = u;                             // 因此u->key[0]将会被删去
        r = 0;
    }
    v->key.remove(r);        // 删除关键码
    v->child.remove(r + 1);  // 以及一个外部结点 ，这里也可以用pop_back,因为都是nullptr
    --size_;
    solveUnderflow(v);
    return true;
}

/**
 * @brief 处理下溢 3种情况
 *      情况1：有左兄弟，尝试向左兄弟借关键码 ，右旋
 *      情况2：向右兄弟借关键码，则v是左，左旋
 *      情况3：左右兄弟要么为空，要么都不够，那么就合并
 * @tparam T
 * @param v
 * @note  这部分设计移动操作比较多，也涉及到了B树的核心原理，如需改动的话，请了解清楚原理
 */
template <typename T>  //关键码删除后若节点下溢，则做节点旋转或合并处理
void BTree<T>::solveUnderflow(BTNodePosi v)
{
    if ((order_ + 1) / 2 <= v->child.size()) return;  // v并没有下溢
    BTNodePosi parent{v->parent};
    if (parent == nullptr) {  // v是根结点
        // 此时到了根结点，并且根节点key为空，且有孩子，那么换根
        if (!v->key.size() && v->child[0] != nullptr) {
            root_ = std::move(v->child[0]);  // 原root_(v)会被销毁
            root_->parent = nullptr;
#ifdef DEBUG
            printf("collapse\n");
#endif
        }
        return;
    }
#ifdef DEBUG
    printf(" ... case 0\n");
#endif
    // 确定parent的第r个孩子是v
    Rank r = 0;
    while (parent->child[r].get() != v) r++;
    // 情况1：有左兄弟，尝试向左兄弟借关键码 ： 右旋
    if (r > 0) {
        BTNodePosi ls{parent->child[r - 1].get()};
        if (ls->child.size() > (order_ + 1) / 2) {  // 左兄弟可以借
#ifdef DEBUG
            printf(" ... case 1\n");
#endif
            v->key.insert(0, std::move(parent->key[r - 1]));  // parent给右孩子(v)
            parent->key[r - 1] = std::move(ls->key.back());  // p拿到最后ls的最大的一个结点
            ls->key.pop_back();

            v->child.insert(0, std::move(ls->child.back()));
            ls->child.pop_back();
            // ls最右侧孩子，作为v的最左侧孩子
            if (v->child[0] != nullptr) v->child[0]->parent = v;
            return;  //右旋完成
        }
    }
    // 情况2：向右兄弟借关键码，则v是左 ：左旋
    if (r + 1 < parent->child.size()) {
        BTNodePosi rs{parent->child[r + 1].get()};  //右兄弟必存在
        if (rs->child.size() > (order_ + 1) / 2) {
#ifdef DEBUG
            printf(" ... case 2\n");
#endif
            // 1. parent的最小的给v
            v->key.push_back(std::move(parent->key[r]));
            // 2. rs的最小点给parent
            parent->key[r] = std::move(rs->key.front());
            rs->key.remove(0);
            // 3. rs的最左侧孩子过继给v,作为v的最右侧孩子
            v->child.push_back(std::move(rs->child.front()));
            rs->child.remove(0);

            if (v->child.back() != nullptr) v->child.back()->parent = v;
            return;
        }
    }
    // 情况3：左右兄弟要么为空，要么都不够，那么就合并
    if (r > 0) {  //存在左兄弟，与左兄弟合并
#ifdef DEBUG
        printf(" ... case 3L\n");
#endif
        BTNodePosi ls{parent->child[r - 1].get()};         // 左兄弟必存在
        ls->key.push_back(std::move(parent->key[r - 1]));  // 将父节点key移动到左边
        parent->key.remove(r - 1);
        // p的第r - 1个关键码转入ls，v不再是p的第r个孩子
        // v剩余的关键码和孩子，全部转入ls
        ls->key.insert(ls->key.end(), std::make_move_iterator(v->key.begin()),
                       std::make_move_iterator(v->key.end()));
        for (auto& child : v->child)
            if (child != nullptr) child->parent = ls;
        ls->child.insert(ls->child.end(), std::make_move_iterator(v->child.begin()),
                         std::make_move_iterator(v->child.end()));
#ifdef DEBUG
        printf("%d v_child_size %d\n",__LINE__, ls->child.size());
        printf("%d child_parent %d\n",__LINE__, parent->child.size());
#endif
        // 删掉右结点v
        parent->child.remove(r);
    } else {  // 与右兄弟合并
#ifdef DEBUG
        printf(" ... case 3R\n");
#endif
        BTNodePosi rs{parent->child[r + 1].get()};  //右兄弟必存在
        rs->key.insert(0, std::move(parent->key[r]));
        parent->key.remove(r);
#ifdef DEBUG
        printf("%dvSize %d, rsSize %d\n",__LINE__, v->child.size(), rs->child.size());
#endif
        // v剩余的关键码和孩子，全部转入ls
        rs->key.insert(rs->key.begin(), std::make_move_iterator(v->key.begin()),
                       std::make_move_iterator(v->key.end()));
        for (auto& child : v->child)
            if (child != nullptr) child->parent = rs;  // 过继孩子

        rs->child.insert(rs->child.begin(), std::make_move_iterator(v->child.begin()),
                         std::make_move_iterator(v->child.end()));
#ifdef DEBUG
        for (auto t : rs->key) printf("%d - ------- ", t);
        printf("\n");
        // 删掉左结点v
        printf("%d child_parent %d\n",__LINE__, parent->child.size());
        printf("%d v_child_size %d\n",__LINE__, rs->child.size());
#endif
        parent->child.remove(r);
    }
    solveUnderflow(parent);  //上升一层，如有必要则继续分裂——至多递归O(logn)层
}
#endif